package hpp.problems;

import hpp.structure.ListNode;

/**
 * 如何判断一个单链表是否有环
 * Created by hpp on 2017/9/8.
 */
public class Problem57 {


    public static void main(String[] args) {
        ListNode root = new ListNode();
        ListNode node1 = new ListNode();
        ListNode node2 = new ListNode();
        ListNode node3 = new ListNode();
        ListNode node4 = new ListNode();
        ListNode node5 = new ListNode();

        root.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;
        node3.data = 3;
        System.out.println(isLoop(root));
        System.out.println(loopLength(root));
        System.out.println(findLoopEntrance(root).data);


    }


    //判断是否有环
    public static Boolean isLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        //如果无环，则fast先走到终点
        //当链表长度为奇数时，fast->Next为空
        //当链表长度为偶数时，fast为空
        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;
            //如果有环，则fast会超过slow一圈
            if (fast == slow) {
                break;
            }
        }

        if (fast == null || fast.next == null)
            return false;
        else
            return true;
    }

    //计算环的长度,在环中，若是快指针走2步，慢指针走1步，则相遇之后再走X步也相遇（同个节点）
    public static int loopLength(ListNode pHead) {
        if (!isLoop(pHead))
            return 0;
        ListNode fast = pHead;
        ListNode slow = pHead;
        int length = 0;
        Boolean begin = false;
        Boolean agian = false;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            //超两圈后停止计数，跳出循环
            if (fast == slow && agian == true)
                break;
            //超一圈后开始计数
            if (fast == slow && agian == false) {
                begin = true;
                agian = true;
            }

            //计数
            if (begin)
                ++length;

        }
        return length;
    }


    //求环的入口点，从相遇点和头结点分别出发，第一次碰面的点就是环的入口点
    public static ListNode findLoopEntrance(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;
            //如果有环，则fast会超过slow一圈
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null)
            return null;
        slow = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

//    如何判断两个链表（不带环）是否相交？将其中的一个链表首尾相连，然后判断另一个链表是否带环即可。

}
